# https://leetcode.cn/problems/gas-station/
# 134. 加油站
# 中等
# 1.5K
# 相关企业
# 在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
#
# 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
#
# 给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        """
        :type gas: List[int]
        :type cost: List[int]
        :rtype: int
        """
        if len(gas) != len(cost):
            return -1

        if len(gas) == 0:
            return 0

        remain_gas = []
        total_len = len(gas)
        for i in range(0, total_len):
            row_remain_gas = [-1] * total_len
            row_remain_gas[i] = gas[i]
            remain_gas.append(row_remain_gas)

        for i in range(0, len(gas)):
            for j in range(1, len(gas)+1):
                col_idx = (i + j) % len(gas)
                pre_col_idx = abs((i + j - 1 + len(gas)) % len(gas))
                if remain_gas[i][pre_col_idx] < 0:
                    remain_gas[i][col_idx] = -1
                else:
                    remain_gas[i][col_idx] = remain_gas[i][pre_col_idx] - cost[pre_col_idx]

                if remain_gas[i][col_idx] >= 0:
                    remain_gas[i][col_idx] = remain_gas[i][col_idx] + gas[col_idx]

        for i in range(0, len(gas)):
            if remain_gas[i][i] >= 0:
                return i

        return -1
